package leetCode.offer42;

public class Solution4 implements Solution{


    /**
     * 此时间复杂度成功的控制在了O(n)
     * @param nums
     * @return
     */
    @Override
    public int maxSubArray(int[] nums) {
        if(nums.length==1) return nums[0];
        if(nums.length==2){
            int sun = nums[0]+nums[1];
            if(sun>nums[0]&&sun>nums[1]){
                return sun;
            }
            return Math.max(nums[0], nums[1]);
        }
        // 存储顺序子数组和
        int[] sum = new int[nums.length+1];
        sum[0] = 0;
        int num = 0;
        for(int i=0;i<nums.length;i++){
            num+=nums[i];
            sum[i+1] = num;
        }
        return maxProfit(sum);
    }

    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int result = -Integer.MAX_VALUE;
        int temResult = -Integer.MAX_VALUE;
        for (int i=0;i<prices.length;i++) {
            if (minPrice > prices[i]) {
                minPrice = prices[i];
            } else if (prices[i] - minPrice > result) {
                result = prices[i] - minPrice;
            }
            if(i<prices.length-1&&temResult<prices[i+1]-prices[i]){
                temResult = prices[i+1] - prices[i];
            }
        }
        if(result == -Integer.MAX_VALUE){
            result = temResult;
        }
        return result;
    }


    public static void main(String[] args) {
        int[] param = {-1,-1,-2,-2};
        System.out.println(new Solution4().maxSubArray(param));
    }

}
